#include <iostream>
#include <vector>

class MemoryPool {
private:
    struct MemoryBlock {
        bool isAllocated;
        size_t size;
        MemoryBlock* next;
    };

    MemoryBlock* head;

public:
    // Constructor
    MemoryPool() : head(nullptr) {}

    // Allocate memory block of given size
    void* allocate(size_t size) {
        MemoryBlock* block = findFreeBlock(size);
        if (block) {
            block->isAllocated = true;
            return reinterpret_cast<void*>(block + 1);
        }

        block = createNewBlock(size);
        block->isAllocated = true;
        return reinterpret_cast<void*>(block + 1);
    }

    // Deallocate memory block
    void deallocate(void* ptr) {
        MemoryBlock* block = reinterpret_cast<MemoryBlock*>(ptr) - 1;
        block->isAllocated = false;
        mergeEmptyBlocks();
    }

private:
    // Find a free memory block of given size
    MemoryBlock* findFreeBlock(size_t size) {
        MemoryBlock* block = head;
        while (block) {
            if (!block->isAllocated && block->size >= size) {
                return block;
            }
            block = block->next;
        }
        return nullptr;
    }

    // Create a new memory block of given size and add it as the head
    MemoryBlock* createNewBlock(size_t size) {
        MemoryBlock* block = reinterpret_cast<MemoryBlock*>(new char[sizeof(MemoryBlock) + size]);
        block->isAllocated = false;
        block->size = size;
        block->next = head;
        head = block;
        return block;
    }

    // Merge consecutive empty memory blocks
    void mergeEmptyBlocks() {
        MemoryBlock* block = head;
        while (block && block->next) {
            if (!block->isAllocated && !block->next->isAllocated) {
                block->size += sizeof(MemoryBlock) + block->next->size;
                block->next = block->next->next;
            }
            else {
                block = block->next;
            }
        }
    }
};

int main() {
    MemoryPool pool;

    int* p1 = static_cast<int*>(pool.allocate(sizeof(int)));
    *p1 = 10;

    int* p2 = static_cast<int*>(pool.allocate(sizeof(int)));
    *p2 = 20;

    pool.deallocate(p1);
    pool.deallocate(p2);

    return 0;
}
